﻿//力扣：257. 二叉树的所有路径
//https://leetcode.cn/problems/binary-tree-paths/description/


//方法：（回溯）
//算法原理：深度优先遍历（DFS）求解。

//路径以字符串形式存储，从根节点开始遍历，每次遍历时将当前节点的值加⼊到路径中，如果该节点为叶⼦节点，将路径存储到结果中。否则，将 "->" 加⼊到路径中并递归遍历该节点的左右⼦树。
//定义⼀个结果数组，进⾏递归。递归具体实现⽅法如下：
//1. 如果当前节点不为空，就将当前节点的值加⼊路径 path 中，否则直接返回；
//2. 判断当前节点是否为叶⼦节点，如果是，则将当前路径加⼊到所有路径的存储数组 paths 中；
//3. 否则，将当前节点值加上 "->" 作为路径的分隔符，继续递归遍历当前节点的左右⼦节点。
//4. 返回结果数组。

//• 特别地，我们可以只使⽤⼀个字符串存储每个状态的字符串，在递归回溯的过程中，需要将路径中的当前节点移除，以回到上⼀个节点。

//具体实现⽅法如下：
//1. 定义⼀个结果数组和⼀个路径数组。
//2. 从根节点开始递归，递归函数的参数为当前节点、结果数组和路径数组。
//	a.如果当前节点为空，返回。
//	b.将当前节点的值加⼊到路径数组中。
//	c.如果当前节点为叶⼦节点，将路径数组中的所有元素拼接成字符串，并将该字符串存储到结果数组中。
//	d.递归遍历当前节点的左⼦树。
//	e.递归遍历当前节点的右⼦树。
//	f.回溯，将路径数组中的最后⼀个元素移除，以返回到上⼀个节点。
//3. 返回结果数组。
class Solution {
public:
    vector<string> ret;                                     // 用于存储所有路径的结果数组
    vector<string> binaryTreePaths(TreeNode* root)
    {
        string path;                                        // 当前路径的字符串表示
        if (root == nullptr)
        {
            return ret;                                     // 如果根节点为空，直接返回空数组
        }

        dfs(root, path);                                    // 调用递归函数，从根节点开始遍历
        return ret;                                         // 返回最终的所有路径
    }

    void dfs(TreeNode* root, string path)
    {
        path += to_string(root->val);                       // 将当前节点的值添加到路径中
        if (root->left == nullptr && root->right == nullptr)// 判断是否为叶子节点（左右子树均为空）
        {
            ret.push_back(path);                            // 如果是叶子节点，将路径加入结果数组
            return;
        }

        path += "->";                                       // 添加路径分隔符

        if (root->left)                                     // 递归处理左子树
        {
            dfs(root->left, path);
        }

        if (root->right)                                    // 递归处理右子树
        {
            dfs(root->right, path);
        }
    }
};